// https://leetcode.cn/problems/sort-array-by-increasing-frequency/
// Created by ade on 2022/9/19.
// 按照频率进行升序排列，如果频率相同，则按照数字倒序排列
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> order1(vector<int> &nums) {
        unordered_map<int, int> m = {};
        for (auto &i : nums) m[i]++;
        vector <pair<int, int>> v = {};
        for (auto &i : m) {
            v.push_back({i.first, i.second});
        }
        sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b) {
            if (a.second < b.second) return true;
            if (a.second == b.second) return a.first > b.first;
            return false;
        });
        vector<int> res = {};
        for (auto &item : v) {
            for (int i = 0; i < item.second; i++) {
                res.push_back(item.first);
            }
        }

        return res;
    }

    vector<int> order(vector<int> &nums) {
        unordered_map<int, int> m = {};
        for (auto &i : nums) m[i]++;
        sort(nums.begin(), nums.end(), [&](int a, int b){
            if(m[a] != m[b]) return m[a] < m[b];
            return a > b;
        });

        return nums;
    }
};

int main() {
    Solution so;
    vector<int> nums = {4, 3, 2, 2, 3, 3, 1, -1};
    vector<int> res = so.order(nums);
    for (auto i : res) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}
